package tree;

/**
 * 二叉排序树和二叉排序树的结点删除
 * @Auther Jun jie Yi
 * @Date 21:05 2021/7/23
 */
public class BSTTree {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        //创建
        Node bst = createBST(arr);
        bst = delNode(bst, 7);
        inOrder(bst);
        //inOrder(searchParent(bst, 2));
    }

    //创建二叉排序树
    public static Node createBST(int[] arr) {
        Node node = new BSTTree().new Node(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            addNode(node, arr[i]);
        }
        return node;
    }

    //添加结点
    public static void addNode(Node node, int r) {
        if(node == null) {
            return;
        }
        if(r < node.val) {
            if(node.left == null) {
                node.left = new BSTTree().new Node(r);
            } else {
                addNode(node.left, r);
            }
        } else {
            if(node.right == null) {
                node.right = new BSTTree().new Node(r);
            } else {
                addNode(node.right, r);
            }
        }
    }

    //删除结点(这里返回删除好的Node结点)
    public static Node delNode(Node root, int val) {
        if(root == null) {
            return null;
        }
        //寻找该结点，如果没有找到返回原数据 root
        Node targetNode = search(root, val);
        if(targetNode == null) {
            return root;
        }
        //如果我们发现该二叉排序树只有一个结点，删除该结点就直接返回 null (引用修改没用，只能加上返回值)
        if(root.left == null && root.right == null) {
            return null;
        }
        //去找到targetNode的父结点
        Node parent = searchParent(root, val);
        //1.如果要删除的结点是叶子结点
        if(targetNode.left == null && targetNode.right == null) {
            //判断targetNode是父结点的左子结点，还是右子结点
            //左子结点
            if(parent.left != null && parent.left.val == val) {
                parent.left = null;
            } else if(parent.right != null && parent.right.val == val) {
                parent.right = null;
            }
        } else if(targetNode.left != null && targetNode.right != null) {
        //2.删除含有两颗子树的结点(这里的删除是右子树找最大的，也可以使用左子树找最小的)
            int midVal = delRightTreeMin(root, targetNode.right);
            targetNode.val = midVal;
        } else {
        //3.删除只有一颗子树的结点
            //如果要删除的结点有左子结点
            if(targetNode.left != null) {
                if(parent != null) {
                    //这里应该加上 parent.left != null
                    if(parent.left != null && parent.left.val == val) {
                        //如果target是parent的左子结点
                        parent.left = targetNode.left;
                    } else {
                        //如果target是parent的右子结点
                        parent.right = targetNode.left;
                    }
                } else {
                    //说明此结点是根结点没有父结点
                    root = targetNode.left;
                }
            } else {
            //如果要删除的结点有右子结点
                if(parent != null) {
                    if(parent.left.val == val) {
                        parent.left = targetNode.right;
                    } else {
                        parent.right = targetNode.right;
                    }
                } else {
                    root = targetNode.right;
                }
            }
        }
        return root;
    }

    //找到树的最小结点删除并返回其值
    public static int delRightTreeMin(Node root, Node target) {
        //循环查找左子结点就可以查到最小的值
        while(target.left != null) {
            target = target.left;
        }
        //这时 node 就指向了最小结点
        //删除这个最小结点并返回这个最小结点的值
        delNode(root, target.val);
        return target.val;
    }

    //查找要删除的结点
    public static Node search(Node node, int val) {
        if(val == node.val) {
            return node;
        } else if(node.left != null && val < node.val) {
                return search(node.left, val);
        } else if(node.right != null && val >= node.val) {
            return search(node.right, val);
        } else {
            return null;
        }
    }

    //查找要删除的父结点
    public static Node searchParent(Node node, int val) {
        if((node.left != null && node.left.val == val) || (node.right != null && node.right.val == val)) {
            return node;
        }
        if(val < node.val && node.left != null) {
            return searchParent(node.left, val);
        } else if(val >= node.val && node.right != null) {
            return searchParent(node.right, val);
        } else {
            return null;
        }
    }

    //中序遍历
    public static void inOrder(Node root) {
        if(root == null) {
            return;
        }
        if(root.left != null) {
            inOrder(root.left);
        }
        if(root.right != null) {
            inOrder(root.right);
        }
    }

    class Node {
        int val;
        Node left;
        Node right;
        public Node(int val) {
            this.val = val;
        }
    }
}
